package hot100;


/*
 * Author：江松
 * Date：2023/4/12 10:34
 *
 前k个高频元素:
1,使用哈希表统计个数：O(低于nLogN)
将键值对加入大顶堆中排序（根据出现次数---值），然后每次取出堆顶，键就是结果

2,如果不使用堆，那么k次循环，每次从哈希表中得到键也可 O(n+k*n)
 */

import java.util.*;

public class Main347 {
    public int[] topKFrequent(int[] nums, int k) {
        int[]res=new int[k];

        HashMap<Integer,Integer>map=new HashMap<>();
        for(int i:nums){
            map.put(i,map.getOrDefault(i,0)+1);
        }

        PriorityQueue<Map.Entry<Integer,Integer>>q=new PriorityQueue<>(new Comparator<Map.Entry<Integer,Integer>>() {
            @Override
            public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
                return o2.getValue().compareTo(o1.getValue());
            }
        });

        for(Map.Entry<Integer,Integer>entry:map.entrySet()){
            q.offer(entry);
        }

        int cnt=0;
        for(int i=0;i<k;++i){
            res[cnt++]=q.poll().getKey();
        }
        return res;
    }
}
